package demo.DataStrucAndAlgo.Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/26-07-26-18:33
 * @Description：demo.DataStrucAndAlgo.Sort       希尔排序
 */
/*
    第一次排序分的组数为 数据总量的0.5倍（取整），之后每一轮排序的组数都是上一次组数的0.5倍（取整），
    直到分到0组停止，如 10位的数据，遵循 5 -> 2 ->1 的分组形式。计组数为group。
    分组完成后再进入从 group~length-1 循环每组中的数据，进行判定。
            交换式：进入循环，该循环从i-group开始，每轮循环i都从group增长到data.length-1，
        使用这里用i-group可以将j值从0~group-1都遍历一次，同时循环以group为周期，
        这样每组中元素都可以被比较到，当发现后面的数据小于前面的数据时，进行交换位置

           移位式：这里类似插入排序，每一组都要进行小范围的，相邻间隔为group的插入排序，
        先保存待排序数据的索引与数据本身，当发现存在逆序时，进入while循环进行移位操作

 */
public class Shell_Sort {

    public static void main(String[] args) {
        int data[] = {5,9,2,3,6,4,7};
        shellSort_Change(data);         //希尔排序_交换法
        System.out.println(Arrays.toString(data));
        System.out.println("---------------------------------------------------------");
        int data2[] = new int[80];
        for (int i = 0; i < 80; i++) {
            data2[i] = (int)(Math.random()*80);
        }
        Date date1 = new Date();
        SimpleDateFormat dataFormat = new SimpleDateFormat("yyyy-MM-dd:HH-mm-ss SSS");
        System.out.println(dataFormat.format(date1));
        shellSort_Shift(data2);          //希尔排序_移位法
        System.out.println(Arrays.toString(data2));
        date1 = new Date();
        System.out.println(dataFormat.format(date1));
    }

    /**
     * 移位法
     *      这里类似插入排序，每一组都要进行小范围的，相邻间隔为group的插入排序，
     *   先保存待排序数据的索引与数据本身，当发现存在逆序时，进入while循环进行移位操作
     * @param data
     */
    public static void shellSort_Shift(int[] data) {
        int j;
        int temp;
        for(int group = data.length/2; group > 0; group = group/2){//每一轮组数为上一轮组数/2求整，10->5->2->1,当小于0后停止排序
            for(int i = group; i < data.length; i++){ //分成group组，每组都要进行移位判定
                //类似于插入排序，不过相邻间隔不是1，而是group
                j = i;
                temp = data[j];
                while(j-group >= 0 && temp<data[j-group]){     //满足下标不越界，当前数据<前一个数据，寻找合适位置
                    data[j] = data[j-group];  //覆盖式的向后移动
                    j = j- group;   //继续搜寻更前的数据
                }
                //跳出循环，表示找到合适位置
                data[j] = temp;  //将数据插入正确位置
            }
        }
    }

    /**
     * 交换法
     *          进入循环，该循环从i-group开始，每轮循环i都从group增长到data.length-1，
     *      使用这里用i-group可以将j值从0~group-1都遍历一次，同时循环以group为周期，
     *      这样每组中元素都可以被比较到，当发现后面的数据小于前面的数据时，进行交换位置
     * @param data
     */
    public static void shellSort_Change(int[] data) {
        int temp = 0;
        int count = 0;
        for(int group = data.length/2; group > 0; group = group/2){  //每一轮数为上一轮组数/2求整，10->5->2->1,当小于0后停止排序
            for (int i = group; i < data.length; i++) {     //分成group组，每组都要进行交换判定
                //每一轮循环i都从group增长到data.length-1，使用这里用i-group可以将j值从0~group-1都遍历一次，同时循环以group为周期，这样每组中元素都可以被比较到
                for(int j = i-group; j >= 0; j = j-group){
                    if(data[j]>data[j+group]){
                        //对每组中的元素进行相邻大小比较，逆序就交换位置，类似冒泡排序
                        temp = data[j];
                        data[j] = data[j+group];
                        data[j+group] = temp;
                    }
                }
            }
        }
    }

}
